題目連結: 20. Valid Parentheses; Easy

題目說明:

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

簡單來說就是判斷字串中左括弧與右括弧是否都成對顯示。

Example1

Input: s = "()"
Output: true

Example2

Input: s = "()[]{}"
Output: true

Example3

Input: s = "(]"
Output: false

Example4

Input: s = "{[]}"
Output: true

Example5

Input: s = "()}}"
Output: false

本次解題心得:

利用Stack後進先出的特性，剛好可以使用在左右成對的比較()、{}、[]，直接排除有問題的配對，不符合題目條件的有哪些呢?

1. 字串是空值or null
2. 字元數不能被2整除
3. 出現左括弧時，若沒有相對應的右括弧

自己的解答:

public class Solution {
    public bool IsValid(string s) {
            if (string.IsNullOrWhiteSpace(s))
                return false;

            if ((s.ToCharArray().Length % 2) != 0) //不是成對的char
                return false;

            Stack<char> st = new Stack<char>(); //使用Stack來存放，特性:先進後出

            foreach (char ch in s)
            {
                if (ch == '(' || ch == '{' || ch == '[')
                    st.Push(ch);

                if (st.Count() == 0) //剛開始與最後，如果出現連續兩個右括弧，Stack.Pop()會出現exception
                    return false;

                if ( ch == ')' && st.Pop() != '(' )
                    return false;

                if (ch == '}' && st.Pop() != '{')
                    return false;

                if (ch == ']' && st.Pop() != '[')
                    return false;
            }

            return st.Count() == 0; //如果Stack還有未配對的括弧，代表false
    }
}

參考別人優化後的解答:

public class Solution {
    public bool IsValid(string s) {
            Stack<char> st = new Stack<char>();

            foreach (var ch in s)
            {
                if (ch == '(') 
                { 
                    st.Push(')'); //右括弧(出現時，把相對應的左括弧)存進Stack
                    continue; //離開迴圈，繼續執行下一字元
                }

                if (ch == '{')
                {
                    st.Push('}'); //右括弧{出現時，把相對應的左括弧}存進Stack
                    continue;
                }

                if (ch == '[')
                {
                    st.Push(']'); //右括弧[出現時，把相對應的左括弧]存進Stack
                    continue;
                }

                if (st.Count == 0 || ch != st.Pop()) //左括弧出現，若沒有相對應的右括弧Pop出來，則表示不成對
                    return false;
            }

            return st.Count() == 0; //如果Stack還有未配對的括弧，表示不成對
    }
}

參考資料來源:
[LeetCode C#] 20. Valid Parentheses — Stack
C# Solution - elegant and simple 7 lines (Runtime: faster than 99.90%; Memory: less than 48.94%)